package doing.doing_001_500;

import lombok.extern.slf4j.Slf4j;
import org.junit.Test;

/**
 * 169. Majority Element 求众数
 * <p>
 * 给定一个大小为 n 的数组，找到其中的众数。
 * 众数是指在数组中出现次数大于 ⌊ n/2 ⌋ 的元素。
 * 你可以假设数组是非空的，并且给定的数组总是存在众数。
 * <p>
 * 示例 1:
 * 输入: [3,2,3]
 * 输出: 3
 * 示例 2:
 * 输入: [2,2,1,1,1,2,2]
 * 输出: 2
 * <p>
 * 这是到求众数的问题，有很多种解法，其中我感觉比较好的有两种，
 * 一种是用哈希表，这种方法需要O(n)的时间和空间，另一种是用一种
 * 叫摩尔投票法 Moore Voting，需要O(n)的时间和O(1)的空间，比
 * 前一种方法更好。这种投票法先将第一个数字假设为众数，然后把计
 * 数器设为1，比较下一个数和此数是否相等，若相等则计数器加一，反
 * 之减一。然后看此时计数器的值，若为零，则将下一个值设为候选众数。
 * 以此类推直到遍历完整个数组，当前候选众数即为该数组的众数。不仔
 * 细弄懂摩尔投票法的精髓的话，过一阵子还是会忘记的，首先要明确的
 * 是这个叼炸天的方法是有前提的，就是数组中一定要有众数的存在才能
 * 使用，下面我们来看本算法的思路，这是一种先假设候选者，然后再进行
 * 验证的算法。我们现将数组中的第一个数假设为众数，然后进行统计其出
 * 现的次数，如果遇到同样的数，则计数器自增1，否则计数器自减1，如果
 * 计数器减到了0，则更换下一个数字为候选者。这是一个很巧妙的设定，
 * 也是本算法的精髓所在，为啥遇到不同的要计数器减1呢，为啥减到0了又
 * 要更换候选者呢？首先是有那个强大的前提存在，一定会有一个出现超过半
 * 数的数字存在，那么如果计数器减到0了话，说明目前不是候选者数字的个
 * 数已经跟候选者的出现个数相同了，那么这个候选者已经很weak，不一定
 * 能出现超过半数，我们选择更换当前的候选者。那有可能你会有疑问，那万
 * 一后面又大量的出现了之前的候选者怎么办，不需要担心，如果之前的候选
 * 者在后面大量出现的话，其又会重新变为候选者，直到最终验证成为正确的
 * 众数，佩服算法的提出者啊
 * 2019-03-24 5:39 PM
 **/
@Slf4j
public class MajorityElement {

    @SuppressWarnings("all")
    public int majorityElement(int[] nums) {
        int res = 0;
        int cnt = 0;

        for (int num : nums) {
            // cnt为0 只有两种可能，
            // 1) 第一次初始化；
            // 2) 由于出现的次数被人超越，计数器归0，res 被重置
            // 3) 只有数量达到超出别人的情况时才会重置 res
            if (cnt == 0) {
                res = num;
                cnt++;
            } else if (num == res) {
                cnt++;
            } else {
                cnt--;
            }
        }
        return res;
    }

    @Test
    public void test() {
        int[] nums = new int[]{5, 5, 3, 2, 5, 5, 6};
        log.info("result:{}", majorityElement(nums));
    }
}




























/*
public int majorityElement(int[] nums) {
    int res = 0;
    int cnt = 0;

    for (int num : nums) {
        // cnt为0 只有两种可能，
        // 1) 第一次初始化；
        // 2) 由于出现的次数被人超越，计数器归0，res 被重置
        // 3) 只有数量达到超出别人的情况时才会重置 res
        if (cnt == 0) {
            res = num;
            cnt++;
        } else if (num == res) {
            cnt++;
        } else {
            cnt--;
        }
    }
    return res;
}
*/
